//给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。 
//
// 假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。 
//
// 注意：每次拼写（指拼写词汇表中的一个单词）时，chars 中的每个字母都只能用一次。 
//
// 返回词汇表 words 中你掌握的所有单词的 长度之和。 
//
// 
//
// 示例 1： 
//
// 输入：words = ["cat","bt","hat","tree"], chars = "atach"
//输出：6
//解释： 
//可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。
// 
//
// 示例 2： 
//
// 输入：words = ["hello","world","leetcode"], chars = "welldonehoneyr"
//输出：10
//解释：
//可以形成字符串 "hello" 和 "world"，所以答案是 5 + 5 = 10。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= words.length <= 1000 
// 1 <= words[i].length, chars.length <= 100 
// 所有字符串中都仅包含小写英文字母 
// 
// Related Topics 数组 哈希表 
// 👍 102 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

import java.util.HashMap;
import java.util.Map;

/**
 * Java：拼写单词
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P1160_FindWordsThatCanBeFormedByCharacters {
    public static void main(String[] args) {
        Solution solution = new P1160_FindWordsThatCanBeFormedByCharacters().new Solution();
        String[] words = {"skwgxuuuumkfurejmqrbipvlavdrozjyxhagbwetabjwevfsegqfpllgafm","ufvpzzgpswnk","tcouxmlrnfyoxvkeglchhryykmdvgvdxpookbtiyhuthoqsnqbowewpfgbcy","qwpttmxzazkkfqqtrnkaejifligdvgnyvtmppjbkeuqryxzqyegttvhzolpztvigxygzvsppurijaekb","vbtvbheurzbglzljczmziitkbmtoybiwhoyfrsxvfveaxchebjdzdnnispzwbrgrbcdaistps"};
        String chars = "avyteswqppomeojxoybotzriuvxolmllevluauwb";
        MyUtil.print(solution.countCharacters(words, chars));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int countCharacters(String[] words, String chars) {
            // 初始化chars map
            Map<Character, Integer> charsMap = new HashMap<>(chars.length());
            for (Character c : chars.toCharArray()) {
                Integer value = charsMap.get(c);
                charsMap.put(c, value == null ? 1 : value + 1);
            }
            // 能拼写的单词map
            Map<Character, Integer> wordsMap = new HashMap<>();
            for (String word : words) {
                // 单词是否记忆的标志
                boolean flag = true;
                // 临时每个单词的记录
                Map<Character, Integer> tempWordsMap = new HashMap<>();
                for (Character c : word.toCharArray()) {
                    Integer charsMapValue = charsMap.get(c);
                    // 找不到字符直接过
                    if (charsMapValue == null) {
                        flag = false;
                        break;
                    }
                    // 临时的个数超了
                    Integer tempMapValue = tempWordsMap.get(c);
                    if (tempMapValue != null && tempMapValue >= charsMapValue) {
                        flag = false;
                        break;
                    }
                    // 记录到临时
                    Integer tempValue = tempWordsMap.get(c);
                    tempWordsMap.put(c, tempValue == null ? 1 : tempValue + 1);
                }
                if (flag) {
                    // 临时的写入能拼写的map
                    tempWordsMap.entrySet().forEach(entry -> {
                        Integer v = wordsMap.get(entry.getKey());
                        wordsMap.put(entry.getKey(), entry.getValue() + (v == null ? 0 : v));
                    });
                }
            }
            int sum = 0;
            for (Integer v : wordsMap.values()) {
                sum += v == null ? 0 : v;
            }
            return sum;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}